﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleAppDemo.sort {
    /// <summary>
    /// 冒泡排序
    /// </summary>
    public class BubbleSort {
        public static void Sort(int[] list)
        {
            int i, j, temp;
            bool done = false;
            j = 1;
            while ((j < list.Length) && (!done))
            {
                done = true;
                for (i = 0; i < list.Length - j; i++)
                {
                    if (list[i] > list[i + 1])
                    {
                        done = false;
                        temp = list[i];
                        list[i] = list[i + 1];
                        list[i + 1] = temp;
                    }
                }
                j++;
            }
        }
    }
    /// <summary>
    /// 选择排序
    /// </summary>
    public class SelectionSort {
        private static int min;
        public static void Sort(int[] list)
        {
            for (int i = 0; i < list.Length - 1; i++)
            {
                min = i;
                for (int j = i + 1; j < list.Length; j++)
                {
                    if (list[j] < list[min])
                        min = j;
                }
                int t = list[min];
                list[min] = list[i];
                list[i] = t;
            }
        }
    }
    /// <summary>
    /// 插入排序
    /// </summary>
    public class InsertSort {
        public void Sort(int[] list)
        {
            for (int i = 1; i < list.Length; i++)
            {
                int t = list[i];
                int j = i;
                while (j > 0 && (list[j - 1] > t))
                {
                    list[j] = list[j - 1];
                    j--;
                }
                list[j] = t;
            }
        }
    }
    /// <summary>
    /// 递归算法
    /// 有一列数1，1，2，3，5，........求第30个数
    /// </summary>
    public class Recursion {
        public static int Foo(int i)
        {
            if (i < 0)
                return 0;
            else if (i > 0 && i <= 2)
                return 1;
            else
                return Foo(i - 1) + Foo(i - 2);
        }
    }
}
